package com.leetcode.algorithm.y22.m08.w2;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 130. 被围绕的区域
 * 
 * https://leetcode.cn/problems/surrounded-regions/
 * 
 * @author jie.deng
 *
 */
class Question0130Solution01 {

	public void solve(char[][] board) {
		Set<Integer> zeroSet = new HashSet<>();
		int rows = board.length;
		int cols = board[0].length;
		Queue<int[]> queue = new LinkedList<>();
		for (int row = 0; row < rows; row++) {
			if (board[row][0] == 'O' && zeroSet.add(row * cols)) {
				queue.add(new int[] { row, 0 });
			}
			if (board[row][cols - 1] == 'O' && zeroSet.add(row * cols + cols - 1)) {
				queue.add(new int[] { row, cols - 1 });
			}
		}
		for (int col = 0; col < cols; col++) {
			if (board[0][col] == 'O' && zeroSet.add(col)) {
				queue.add(new int[] { 0, col });
			}
			if (board[rows - 1][col] == 'O' && zeroSet.add((rows - 1) * cols + col)) {
				queue.add(new int[] { rows - 1, col });
			}
		}

		int[][] directions = new int[][] { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int k = 0; k < size; k++) {
				int[] arr = queue.poll();
				int row = arr[0];
				int col = arr[1];
				for (int[] dir : directions) {
					int r = row + dir[0];
					int c = col + dir[1];
					if (r >= 0 && r < rows && c >= 0 && c < cols) {
						if (board[r][c] == 'O') {
							if (zeroSet.add(r * cols + c)) {
								queue.offer(new int[] { r, c });
							}
						}
					}
				}
			}
		}

		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				if (board[i][j] == 'O' && !zeroSet.contains(i * cols + j)) {
					board[i][j] = 'X';
				}
			}
		}

	}

}